//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//typedef pair<LL, LL> PLL;
//int main() {
//	double sum1 = 0,sum2=0;
//	int n;
//	cin >> n;
//	while (n--)
//	{
//		double a, b;
//		cin >> a >> b;
//		sum1 += a * b;
//		sum2 += a;
//	}
//	printf("%.6lf", sum1 / sum2);
//	}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//unordered_map<string, string>mp;
//vector<string>v;
//int main() {
//	int n, q;
//	cin >> n >> q;
//	for (int i = 0; i < n; i++)
//	{
//		string s;
//		cin >> s;
//		v.push_back(s);
//		string s1;
//		for (int j = 0; j < s.size(); j++)
//		{
//			if (s[j] >= 'A' && s[j] <= 'Z')
//				s1 += s[j];
//		}
//		mp[s1] = mp[s1] + to_string(i) + 'a';
//	}
//	for (int i = 0; i < q; i++)
//	{
//		string s;
//		cin >> s;
//		/*if (mp[s] == "")
//			cout << 0 << endl;*/
//		s = mp[s];
//		vector<string>vv;
//		for (int i = 0; i < s.size(); i++)
//		{
//			string s1;
//			while (i<s.size()&&s[i] != 'a')
//				s1 += s[i++];
//			int x = stoi(s);
//			vv.push_back( v[x]);
//		}
//		cout << vv.size() << endl;
//		for (auto i : vv)
//			cout << i << endl;
//	}
//}
//#include<bits/stdc++.h>
//using namespace std;
//vector<vector<pair<int, int>>>v(1010, vector<pair<int, int>>());
//int main() {
//    int n, m, k;
//    cin >> n >> m >> k;
//    for (int i = 1; i <= n; i++)
//    {
//        int x, y;
//        cin >> x >> y;
//        v[x].push_back({ i,y });
//    }
//    for (int i = 1; i <= m; i++)
//    {
//        if (v[i].size() == 0)
//            cout << -1 << endl;
//        else {
//            for (int j = 0; j < v[i].size(); j++)
//                for (int k = 0; k < v[i].size() - 1; k++)
//                    if (v[i][k].second < v[i][k + 1].second)
//                        swap(v[i][k], v[i][k + 1]);
//            for (int j = 0; j < v[i].size(); j++)
//                cout << v[i][j].first << ' ';
//            cout << endl;
//        }
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[500010];
//int main() {
   /* int n;
    cin >> n;
    arr[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        if (arr[i] < 0)
            arr[i] = arr[i - 1];
        else
        arr[i] |= arr[i - 1];
    }
    LL q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << (arr[r]-arr[l])<< endl;*/
    //}
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[500010];
//int main() {
//    int n;
//    cin >> n;
//    arr[0] = 0;
//    for (int i = 1; i <= n; i++) {
//        cin >> arr[i];
//    }
//    int q;
//    cin >> q;
//    for (int i = 1; i <= q; i++)
//    {
//        int l, r;
//        cin >> l >> r;
//        int j = 0;
//        while (l <= r)
//            if (arr[l] < 0) { l++; continue; }
//            else
//            j |= arr[l++];
//        cout << j << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 5e5 + 10;
//LL arr[61][N];
//LL brr[N];
//int main() {
//    int n;
//    cin >> n;
//    for (int i = 1; i <= n; i++) {
//        cin >> brr[i];
//        if (brr[i] < 0)
//            brr[i] = 0;
//    }
//    for (int i = 0; i<=60; i++)
//        for (int j = 1; j <= n; j++)
//            arr[i][j] =arr[i][j-1]+ ((brr[j]>>i)&1);
//    int q;
//    cin >> q;
//    for (int i = 1; i <= q; i++)
//    {
//        LL ans = 0;
//        int l, r;
//        cin >> l >> r;
//        for (int i = 0; i <= 60; i++)
//            ans +=((LL)1 << i) * (arr[i][r] - arr[i][l - 1] ? 1 : 0);
//        cout << ans << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//LL arr[N];
//int n;
//bool check(int len)
//{
//    LL x = 2* len + arr[0];
//    int i = 0;
//    for ( i = 0; i < n; i++)
//        if (arr[i] > x)
//            break;
//    if (i == n)return 1;
//    x = arr[i] + 2 * len;
//    for (; i < n; i++)
//        if (arr[i] > x)
//            break;
//    if (i == n)return 1;
//    x = arr[i] + 2 * len;
//    for (; i < n; i++)
//        if (arr[i] > x)
//            break;
//    if (i == n)return 1;
//    return 0;
//}
//void slove() {
//    cin >> n;
//    for (int i = 0; i < n; i++)cin >> arr[i];
//    sort(arr, arr + n);
//    LL l = 0, r = arr[n - 1]-arr[0];
//    while (l < r)
//    {
//        LL mid = l + r >> 1;
//        if (check(mid))
//            r = mid;
//        else
//            l = mid + 1;
//    }
//    cout << l << endl;
//}
//int main() {
//    int t;
//    cin >> t;
//    while (t--)
//        slove();
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e5 + 10;
//int arr[N];
//int dp[N][8];
//int main() {
//    int n, m;
//    cin >> n >> m;
//    memset(dp, 0x3f, sizeof dp);
//    for (int i = 1; i <= 7; i++)dp[0][i] = 0;
//    for (int i = 1; i <= n; i++)cin >> arr[i];
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= 7; j++)
//            for (int k = 1; k <= 7; k++)
//            {
//                if (abs(j - k) <= m)
//                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + (j != arr[i]));
//            }
//    int Min = 2e9;
//    for (int i = 1; i <= 7; i++)
//        Min = min(Min, dp[n][i]);
//    cout << Min;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[1000010], brr[1000010];
//
//int main() {
//    int n, m, q;
//    cin >> n >> m >> q;
//    int crr[100][ 100] = { 0 };
//    for (int i = 0; i < q; i++)
//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//        if (x == 1)
//        {
//            if (y == 1)
//                arr[z] = i;
//            else
//                brr[z] = i;
//        }
//        else
//        {
//            crr[y][z] = i;
//            crr[ y][ z-1] = i;
//            crr[ y][ z + 1] = i;
//            crr[y + 1][z] = i;
//            crr[ y-1][z] = i;
//        }
//    }
//    int ans = 0;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            if (crr[i][j] > max(arr[i], brr[j]))
//                ans++;
//        }
//    cout<<ans;
//}